package basic.courseLearn05.binaryTree;

import basic.courseLearn05.TreeNode;
import basic.courseLearn05.Utils;
import org.junit.Test;

import java.util.Stack;

public class ErgodicTree {


    //打印二叉树
    @Test
    public void test() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        new Utils().treePrint(root);
        System.out.print("前序遍历-递归：");
        preOrder_recursive(root);
        System.out.print("\n前序遍历-非递归：");
        preOrder_notRecursive(root);
        System.out.print("\n中序遍历-递归：");
        inOrder_recursive(root);
        System.out.print("\n中序遍历-非递归：");
        inOrder_notRecursive(root);
        System.out.print("\n后序遍历-递归：");
        postOrder_recursive(root);
        System.out.print("\n后序遍历-非递归：");
        postOrder_notRecursive(root);
    }

    //前序遍历，递归实现
    public void preOrder_recursive(TreeNode node) {
        if (node!= null) {
            System.out.print(node.value + " ");
            preOrder_recursive(node.left);
            preOrder_recursive(node.right);

        }
    }

    //中序遍历，递归实现
    public void inOrder_recursive(TreeNode node) {
        if (node!= null) {
            inOrder_recursive(node.left);
            System.out.print(node.value + " ");
            inOrder_recursive(node.right);

        }
    }

    //后序遍历，递归实现
    public void postOrder_recursive(TreeNode node) {
        if (node!= null) {
            postOrder_recursive(node.left);
            postOrder_recursive(node.right);
            System.out.print(node.value + " ");
        }
    }

    //前序遍历，非递归实现
    public void preOrder_notRecursive(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            System.out.print(cur.value + " ");
            if (cur.right!= null) {
                stack.push(cur.right);
            }
            if (cur.left!= null) {
                stack.push(cur.left);
            }
        }
    }

    //中序遍历，非递归实现
    public void inOrder_notRecursive(TreeNode node) {
        if (node == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        //所有的左节点都入栈
        while(node!=null){
            stack.push(node);
            node=node.left;
        }
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            System.out.print(cur.value + " ");
            if (cur.right!= null) {
                TreeNode tempNode=cur.right;
                while(tempNode!=null){
                    stack.push(tempNode);
                    tempNode=tempNode.left;
                }
            }

        }
    }

    //后序遍历，非递归实现
    public void postOrder_notRecursive(TreeNode node) {
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        if (node==null){
            return;
        }
        s1.push(node);
        while (!s1.isEmpty()){
            TreeNode cur = s1.pop();
            s2.push(cur);
            if (cur.left!=null){
                s1.push(cur.left);
            }
            if (cur.right!=null){
                s1.push(cur.right);
            }
        }
        while (!s2.isEmpty()){
            TreeNode cur = s2.pop();
            System.out.print(cur.value + " ");
        }
    }




}
